/* 100. 相同的树 */
function TreeNode(val, left, right) {
	this.val = val == null ? 0 : val
	this.left = left == null ? null : left
	this.right = right == null ? null : right
}
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
/* 深度优先搜索 */
var isSameTree = function (p, q) {
	if (p == null && q == null) {
		return true
	} else if (p == null || q == null) {
		return false
	} else if (p.val !== q.val) {
		return false
	} else {
		return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
	}
}

/* 

    广度优先搜索
    层序遍历
*/
var isSameTree = function (p, q) {
	if (p == null && q == null) return true
	if (p == null || q == null) return false
	let queue = [p, q],
		node1,
		node2
	while (queue.length) {
		node1 = queue.shift()
		node2 = queue.shift()

		if (!node1 && !node2) continue
		if (!node1 || !node2 || node1.val !== node2.val) return false

		/* 
            如果两个节点的子节点结果相同则将两个非空子节点分别加入
            队列 都不为空的时候先加入左子节点后加入右子节点
        */
		queue.push(node1.left)
		queue.push(node2.left)
		queue.push(node1.right)
		queue.push(node2.right)
	}

	return true
}
